|
A root-finding algorithm is a numerical method, or algorithm, for finding a value ''x'' such that ''f''(''x'') = 0, for a given function ''f''. Such an ''x'' is called a root of the function ''f''. This article is concerned with finding scalar, real or complex roots, approximated as floating point numbers. Finding integer roots or exact algebraic roots are separate problems, whose algorithms have little in common with those discussed here. (See: Diophantine equation for integer roots) Finding a root of ''f''(''x'') − ''g''(''x'') = 0 is the same as solving the equation ''f''(''x'') = ''g''(''x''). Here, ''x'' is called the ''unknown'' in the equation. Conversely, any equation can take the canonical form ''f''(''x'') = 0, so equation solving is the same thing as computing (or ''finding'') a root of a function. Numerical root-finding methods use iteration, producing a sequence of numbers that hopefully converge towards a limit, which is a root. The first values of this series are ''initial guesses''. Many methods computes subsequent values by evaluating an auxiliary function on the preceding values. The limit is thus a fixed point of the auxiliary function, which is chosen for having the roots of the original equation as fixed points. The behaviour of root-finding algorithms is studied in numerical analysis. Algorithms perform best when they take advantage of known characteristics of the given function. Thus an algorithm to find isolated real roots of a low-degree polynomial in one variable may bear little resemblance to an algorithm for complex roots of a "black-box" function which is not even known to be differentiable. Questions include ability to separate close roots, robustness against failures of continuity and differentiability, reliability despite inevitable numerical errors, and rate of convergence. == Bracketing methods == Bracketing methods track the end points of an interval containing a root. This allows them to provide absolute error bounds on a root's location when the function is known to be continuous. Bracketing methods require two initial conditions, one on either side of the root. 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Root-finding algorithm」の詳細全文を読む スポンサード リンク
|